class Solution {
    int left,right,pos;
    vector<string> ret;
    string path;
public:
    vector<string> generateParenthesis(int n) {
        pos=n;
        dfs();
        return ret;
    }
    void dfs()
    {
        if(right==pos)
        {
            ret.push_back(path);
            return;
        }
    if(left<pos)
    {
        path.push_back('(');
        left++;
        dfs();
        path.pop_back();
        left--;
    }
    if(right<left)
    {
        path.push_back(')');
        right++;
        dfs();
        path.pop_back();
        right--;
    }

    }
};

